إيه هي الـ Lists؟

• الـ List هي مجموعة من البيانات المرتبة (Ordered Data).
  • ممكن تحتوي على صفر أو أكتر من العناصر.
  • العناصر بتكون محطوطة بين أقواس مربعة [ ] وبتتصل ببعضها بفاصلة ,.

أمثلة:

• ا [12, city, ann, bb] -> دي List فيها 4 عناصر.
• ا [a] -> دي List فيها عنصر واحد بس.
• ا [] -> دي Empty List (قايمة فاضية).
• ا [34, tom, [2,3]] -> دي List فيها 3 عناصر، والعنصر التالت عبارة عن List جواها عنصرين.

الـ Head والـ Tail

• أي List (مش فاضية) نقدر نقسمها لجزأين أساسيين:
  1. الـ Head (الرأس): هو أول عنصر في الـ List.
  2. الـ Tail (الديل): هو باقي عناصر الـ List، ودايمًا الـ Tail لازم يكون List.

• عشان نفصل الـ Head عن الـ Tail في Prolog بنستخدم الرمز | (Vertical bar):

|?- [a, b, c, d] = [Head | Tail].
Head = a, Tail = [b, c, d].

|?- [a] = [H | T].
H = a, T = [].   %  the Tail of one element is an Empty List

|?- [] = [H | T].
false.           %  Empty List does not have a Head or a Tail

|?- [H1, H2 | Tail] = [mia, vincent, jules, yolanda].
H1 = mia, H2 = vincent, Tail = [jules, yolanda].

الـ List Unification (التطابق)

• الـ Lists ممكن يحصلها Unify (تتطابق) مع متغيرات أو مع Lists تانية.
• عشان يحصل Unification بين 2 Lists، لازم يكون عندهم نفس الطول، وكل عنصر في الـ List الأولى يقدر يحصله Unify مع العنصر اللي بيقابله في الـ List التانية.

أمثلة:

|?- [Any, list, 'of elements'] = X.
X = [Any, list, 'of elements'].

|?- [a, B, c, D] = [A, b, C, d].
A = a, B = b, C = c, D = d.

|?- [[X, a]] = [b, Y].
false.      % طول الأولى 1 (فيها ليست واحدة)، وطول التانية 2

|?- [(a+X), (Y+b)] = [(W+c), (d+b)].
W = a, X = c, Y = d.

العمليات الأساسية على الـ Lists (List Operations)

• العمليات دي تعتبر أهم جزء في الـ Lists، وكلها بتعتمد على فكرة الـ Recursion (إن الـ Rule بتنادي نفسها) وإننا بنقسم الـ List لـ Head و Tail. دلوقتي هنفهم كل عملية بتشتغل إزاي بالتفصيل:

1. الـ Membership (الانتماء) member

• العملية دي بتجاوب على سؤال: "هل العنصر ده موجود جوه الـ List ولا لأ؟"

• عشان نعرف بتشتغل ازاي هنقسم الموضوع لجزئين:

  1. الـ Base Case (حالة التوقف): أنا بصيت في أول الليست (الـ Head) ولقيت الحاجة اللي بدور عليها.
  2. الـ Recursive Case (حالة التكرار): الحاجة الي بدور عليها مش في أول الليست، فهسيب اول الليست (الـ Head) وأروح أدور في باقي الليست (الـ Tail).

• الحالة الأولى: العنصر X هو الـ head بتاع الليست:

member(X, [X | Tail]).                   

• الحالة التانية: العنصر X مش هو الـ head ، فهنروح ندور عليه في الـ Tail

member(X, [Head | Tail]) :- member(X, Tail). 

• فيبقي التعريف الكامل بتاعها :

member(X, [X | Tail]).    
member(X, [Head | Tail]) :- member(X, Tail).                

2. الـ Concatenation (الدمج) append

• بتستخدم عشان ندمج 2 lists في بعض ونطلع بـ List تالتة. append(L1, L2, L3).
• فكرتها إننا بناخد عناصر اول List نشيلهم على جنب، لحد ما اول List تفضى، وبعدين ندمجها مع التانية، وبعدين نرجع العناصر اللي شيلناها.

1. الـ Base Case: لو الـ List الأولى فاضية []، يبقى لو لزقناها مع أي List تانية L هيدينا نفس الـ List التانية L.
2. الـ Recursive Case: لو الـ List الأولى مش فاضية، بناخد الـ Head بتاعها نحطه كـ Head للناتج النهائي، ونعمل append للـ Tail بتاعها مع الـ List التانية.

• لو الأولى فاضية، الناتج هو التانية

append([], L, L).

• بناخد X من الأولى نحطه في الناتج، ونكمل دمج لباقي الأولى (L1) مع التانية (L2)

append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).

• فيبقي التعريف الكامل :

append([], L, L).
append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).

?- append(L1, L2, [a,b,c]).
L1= [], L2 = [a,b,c];
L1= [a], L2= [b,c];
L1 = [a,b], L2 = [c];
L1 = [a,b,c], L2 = [];

3. الإضافة والحذف (Adding & Deleting)

الإضافة (Adding) add:

• دي اسهل شوية, لو عايز تضيف عنصر X على List اسمها L، حطه هو الـ Head، وخلي L هي الـ Tail في List جديدة.

add(X, L, [X | L]).
% ?- add(5, [1,2], L). -> L = [5, 1, 2].

الحذف (Deleting) del:

• شبه الـ member شوية، بنمشي ندور علي العنصر المطلوب بس لما بنلاقيه بدل ما بنجاوب بـاننا لقيناه، إحنا بنشيل العنصر ونرجع الـ List من غيره:

  1. لو العنصر X هو الـ Head، يبقى الـ List الجديدة هي الـ Tail وخلاص كده.
  2. لو العنصر X مش هو الـ Head، يبقى هنحتفظ بالـ Head زي ما هو Y، وننادي الدالة تاني تروح تمسح X من الـ Tail.

• مسحنا X عشان هو الـ Head، ورجعنا Tail

del(X, [X | Tail], Tail).

• احتفظنا بـ Y، ورحنا نمسح X من الـ Tail عشان نجيب Tail1 الجديد

del(X, [Y | Tail], [Y | Tail1]) :- del(X, Tail, Tail1).

• فيبقي التعريف الكامل :

del(X, [X | Tail], Tail).
del(X, [Y | Tail], [Y | Tail1]) :- del(X, Tail, Tail1).

• (ملاحظة: لو العنصر X متكرر جوه الـ List، الـ Prolog بيمسح أول واحد يقابله، ولو دوست ; هيرجعلك الاحتمالات التانية إنه يمسح النسخ التانية ويسيب الأولى).

insert(X, L, BiggerList) :- del(X, BiggerList, L).

4. الـ Sublist sublist

• عشان نختبر هل الـ List اللي اسمها S موجودة جوه الـ List الكبيرة L (بنفس الترتيب).
• بنستخدم الـ append مرتين كأننا بنقطع الـ List الكبيرة حتت:
  1. بنقسم الـ L الكبيرة لجزأين: L1 و L2.
  2. بناخد الـ L2 نقسمها لجزأين: S (اللي بندور عليها) و L3 (الباقي).
• لو عرفنا نعمل التقسيمة دي، يبقى أكيد S موجودة جوه L.

sublist(S, L) :- append(L1, L2, L), append(S, L3, L2).

الـ Sublist بتدور على الـ عناصر ورا بعض بنفس الترتيب.

مثال (1): هل دي Sublist ولا لأ؟

?- sublist([c,d,e], [a,b,c,d,e,f]).
true.

(عشان c,d,e موجودين ورا بعض).

مثال (2): العناصر موجودة بس مش ورا بعض!

?- sublist([c,e], [a,b,c,d,e,f]).
false.

(هيديك false لأن c و e مش ورا بعض في الليست الأساسية، مفصولين بـ d).

5. التباديل (Permutations) permutation

• لو عندنا List وعايزين نجيب كل الترتيبات (التباديل) الممكنة لعناصرها.
• الفكرة بتاعتها:
  1. لو الـ List فاضية، تباديلها هي قايمة فاضية.
  2. لو فيها عناصر، بناخد أول عنصر X على جنب، ونجيب التباديل بتاعة باقي الـ List L1، وبعدين نحط العنصر X في كل الأماكن الممكنة جوه الـ L1.

permutation([], []).
permutation([X | L], P) :- permutation(L, L1), insert(X, L1, P).

مثال (1): تباديل لعنصرين:

?- permutation([a,b], P). 
P = [a, b] ;
P = [b, a] ;
false.

مثال (2): تباديل لـ 3 عناصر:

?- permutation([red, blue, green], P). 
P = [red, blue, green]; 
P = [red, green, blue]; 
P = [blue, red, green]; 
P = [blue, green, red]; 
P = [green, red, blue]; 
P = [green, blue, red]; 
false.

Arithmetic and Lists

• دي شوية أمثلة وتطبيقات جاهزة في الـ Prolog للتعامل مع الـ Lists:

1. لو عايزين نجيب طول الـ List (Length):

• الـ Prolog فيها الدالة الجاهزة length بس إحنا في المنهج غاويين وجع دماغ وهنكتبها بنفسنا:

len([], 0).
len([_ | L], N) :- len(L, X), N is X + 1.

2. عكس الـ List (Reverse):
   الدالة الجاهزة reverse، تعريفها:

nrev([], []).
nrev([H | T], R) :- nrev(T, RevT), append(RevT, [H], R).

3. جمع عناصر الـ List (Sumlist):
   عشان نجمع الأرقام اللي جوه الـ List:

sumlist([], 0).
sumlist([H | T], N) :- sumlist(T, N1), N is N1 + H.

4. اختبار إن طول الـ List زوجي (Even):
   بنسحب كل مرة عنصرين، لحد ما نوصل لقايمة فيها عنصرين أو قايمة فاضية.

even([_,_]).
even([_,_ | T]) :- even(T).

Nour Eldeen Mahmoud